package com.yuting.practice.sort;

public class quickSort {


    public static void quickSort(int[] arr, int left, int right){

        if(left >= right){
            return;
        }

        int partition = partition(arr, left, right);

        quickSort(arr, left, partition - 1);
        quickSort(arr, partition + 1, right);


    }


    public static int partition(int[] arr, int left1, int right1){
         int pivat = arr[left1];

         int left = left1;
         int right = right1;

         while(left < right){

             while(arr[left] <= pivat && left < arr.length - 1){
                 left++;
             }

             while(arr[right] > pivat && right > 0){
                 right--;
             }
            swap(arr, left, right);

         }

         swap(arr,left,right);

         swap(arr,left1, right);

         return right;
    }

    public static void swap(int[] arr, int index1, int index2){
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void main(String[] args) {
       int[] a = {3,5,76,2,1,6,4};

       quickSort(a, 0, a.length - 1);
//        int partition = partition(a, 0, a.length - 1);
//        System.out.println("par"+partition);
        for (int i :
                a) {
            System.out.println(i);
        }


    }



}
